#include <iostream>
#include <string>
#include <vector>
using namespace std;
int sub(string &str, int n)
{
    // 1 先有一个数组
    vector<int> next(n, 0); // 开辟这么多个空间 ，然后用0初始化
    for (int i = 1; i < n; i++)
    {

        int j = next[i - 1]; // 这个是比较的指针从上一次比较的位置开始比较
        // 然后接下来分为两种情况比较的上和比较不上
        while (j > 0 && str[i] != str[j])
        {
            // 比较不上就回溯
            j = next[j - 1]; // 看懂这一步一定要的前提就是知道上一步int j = next[i - 1];
        }
        if (str[i] == str[j])
        {
            j++;
        }
        next[i] = j;
    }
    return next[n - 1];
}


int main()
{
    string s;
    cout << "请输入一个字符串: ";
    cin >> s;

    int len = sub(s, s.size());
    cout << "最长公共前后缀的长度: " << len << endl;

    if (len > 0)
    {
        cout << "最长公共前后缀子串: " << s.substr(0, len) << endl;
    }
    else
    {
        cout << "无公共前后缀" << endl;
    }
    return 0;
}
